package org.wuxinshui.boosters.nowcoder.classicQuestion;

import java.util.HashMap;
import java.util.Map;

/**
 * 描述
 *
 * 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
 *
 * 数据范围：
 * n
 * ≤
 * 10000
 * n≤10000，
 * 1
 * <
 * =
 * 结
 * 点
 * 值
 * <
 * =
 * 10000
 * 1<=结点值<=10000
 *
 * 要求：空间复杂度
 * O
 * (
 * 1
 * )
 * O(1)，时间复杂度
 * O
 * (
 * n
 * )
 * O(n)
 *
 *
 *
 * 例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：
 *
 *
 * 可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
 * 输入描述：
 *
 * 输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
 * 返回值描述：
 *
 * 返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
 * 示例1
 *
 * 输入：
 * {1,2},{3,4,5}
 * 复制
 * 返回值：
 * 3
 * 复制
 * 说明：
 * 返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3
 * 示例2
 *
 * 输入：
 * {1},{}
 * 复制
 * 返回值：
 * "null"
 * 复制
 * 说明：
 * 没有环，返回对应编程语言的空结点，后台程序会打印"null"
 * 示例3
 *
 * 输入：
 * {},{2}
 * 复制
 * 返回值：
 * 2
 * 复制
 * 说明：
 * 环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2
 */
public class CC9EntryNodeOfLoop_Practice {

    /**
     * 找出链表中环的入口结点
     * 使用快慢指针法（Floyd环检测算法）
     *
     * @param pHead 链表头节点
     * @return 环的入口结点，如果无环则返回null
     */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }

        // 步骤1：检测链表中是否有环
        ListNode meetingNode = getMeetingNode(pHead);
        if (meetingNode == null) {
            return null; // 没有环
        }

        // 步骤2：找到环的入口
        return findLoopEntry(pHead, meetingNode);
    }

    /**
     * 使用快慢指针检测环，并返回相遇节点
     */
    private ListNode getMeetingNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;        // 慢指针每次走一步
            fast = fast.next.next;   // 快指针每次走两步

            if (slow == fast) {
                return slow; // 相遇，说明有环
            }
        }

        return null; // 没有环
    }

    /**
     * 找到环的入口节点
     * 原理：当快慢指针相遇后，将其中一个指针重置到头节点，
     * 然后两个指针以相同速度前进，再次相遇的节点就是环的入口
     */
    private ListNode findLoopEntry(ListNode head, ListNode meetingNode) {
        ListNode ptr1 = head;
        ListNode ptr2 = meetingNode;

        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }

        return ptr1; // 环的入口节点
    }

    // ==================== 测试辅助方法 ====================

    /**
     * 根据输入构建链表
     * @param preArray 环前部分的节点值数组
     * @param cycleArray 环部分的节点值数组
     * @return 构建的链表头节点
     */
    public ListNode buildLinkedList(int[] preArray, int[] cycleArray) {
        if (preArray == null && cycleArray == null) {
            return null;
        }

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        Map<Integer, ListNode> nodeMap = new HashMap<>();

        // 构建环前部分
        ListNode cycleEntry = null;
        if (preArray != null) {
            for (int val : preArray) {
                current.next = new ListNode(val);
                current = current.next;
                nodeMap.put(val, current);
            }
        }

        // 构建环部分
        if (cycleArray != null && cycleArray.length > 0) {
            // 记录环的入口节点（环的第一个节点）
            cycleEntry = new ListNode(cycleArray[0]);
            nodeMap.put(cycleArray[0], cycleEntry);

            // 如果环前部分不为空，将最后一个节点指向环入口
            if (current != dummy) {
                current.next = cycleEntry;
            } else {
                // 如果环前部分为空，头节点就是环入口
                dummy.next = cycleEntry;
            }

            current = cycleEntry;

            // 构建环的其他节点
            for (int i = 1; i < cycleArray.length; i++) {
                int val = cycleArray[i];
                if (nodeMap.containsKey(val)) {
                    // 如果节点已存在，说明环闭合
                    current.next = nodeMap.get(val);
                } else {
                    current.next = new ListNode(val);
                    current = current.next;
                    nodeMap.put(val, current);
                }
            }

            // 将环的最后一个节点指向环入口，形成环
            if (cycleArray.length > 1) {
                current.next = cycleEntry;
            } else {
                // 只有一个节点时，形成自环
                current.next = current;
            }
        }

        return dummy.next;
    }

    /**
     * 解析输入字符串并构建链表
     */
    public ListNode parseAndBuild(String input) {
        // 解析输入格式：{1,2},{3,4,5}
        String[] parts = input.split("\\},\\{");

        int[] preArray = null;
        int[] cycleArray = null;

        // 解析环前部分
        if (parts.length > 0) {
            String preStr = parts[0].replace("{", "").replace("}", "");
            if (!preStr.isEmpty()) {
                String[] preValues = preStr.split(",");
                preArray = new int[preValues.length];
                for (int i = 0; i < preValues.length; i++) {
                    preArray[i] = Integer.parseInt(preValues[i]);
                }
            }
        }

        // 解析环部分
        if (parts.length > 1) {
            String cycleStr = parts[1].replace("{", "").replace("}", "");
            if (!cycleStr.isEmpty()) {
                String[] cycleValues = cycleStr.split(",");
                cycleArray = new int[cycleValues.length];
                for (int i = 0; i < cycleValues.length; i++) {
                    cycleArray[i] = Integer.parseInt(cycleValues[i]);
                }
            }
        }

        return buildLinkedList(preArray, cycleArray);
    }

    // ==================== 测试代码 ====================

    public static void main(String[] args) {
        CC9EntryNodeOfLoop_Practice solution = new CC9EntryNodeOfLoop_Practice();

        // 测试用例1: {1,2},{3,4,5} -> 环入口值为3
        System.out.println("=== 测试用例1 ===");
        ListNode head1 = solution.parseAndBuild("{1,2},{3,4,5}");
        ListNode entry1 = solution.EntryNodeOfLoop(head1);
        System.out.println("环入口节点值: " + (entry1 != null ? entry1.val : "null"));

        // 测试用例2: {1},{} -> 无环
        System.out.println("\n=== 测试用例2 ===");
        ListNode head2 = solution.parseAndBuild("{1},{}");
        ListNode entry2 = solution.EntryNodeOfLoop(head2);
        System.out.println("环入口节点值: " + (entry2 != null ? entry2.val : "null"));

        // 测试用例3: {},{} -> 无环
        System.out.println("\n=== 测试用例3 ===");
        ListNode head3 = solution.parseAndBuild("{},{}");
        ListNode entry3 = solution.EntryNodeOfLoop(head3);
        System.out.println("环入口节点值: " + (entry3 != null ? entry3.val : "null"));

        // 测试用例4: {},{2} -> 环入口值为2
        System.out.println("\n=== 测试用例4 ===");
        ListNode head4 = solution.parseAndBuild("{},{2}");
        ListNode entry4 = solution.EntryNodeOfLoop(head4);
        System.out.println("环入口节点值: " + (entry4 != null ? entry4.val : "null"));

        // 测试用例5: 复杂环
        System.out.println("\n=== 测试用例5 ===");
        ListNode head5 = solution.buildLinkedList(
                new int[]{1, 2, 3, 4},
                new int[]{5, 6, 7, 8}
        );
        ListNode entry5 = solution.EntryNodeOfLoop(head5);
        System.out.println("环入口节点值: " + (entry5 != null ? entry5.val : "null"));
    }

   static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
